\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input mac.tex
\input mathmac.tex

\def\Hom#1#2#3{\mathrm{Hom}_{#1}(#2, #3)}
\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
\def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}}
\def\rmder#1{{\ \buildrell  \Longrightarrow \over{rm}}^{#1}\ }
\def\lmder#1{\buildrel #1\over{\buildrell  \Longrightarrow \over{lm}}}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Homework 5\\}
\vspace{0.5cm}
\textbf{Jian Chang, Sanjian Chen, Yeming Fang}\\
\vspace{0.2cm}
\itshape{ \{jianchan,sanjian,yemingf\}}@\itshape{cis.upenn.edu}
\end{center}

\vspace {0.25cm}
\noindent
{\bf Problem B1 Proof:}

\begin{itemize}
  \item For $L_1$.\\

        Following the hint, consider $a^mb^nc^p$ with $m$ large, and let
   the $a$'s be distinguished. By Ogden's lemma, for every string $w \in L_1$
   such that $w = a^mb^nc^p$, there exists a decomposition $w = uvxyz$, and the
   following properties hold.
   \begin{enumerate}
	    \item There are $A \in N$ and derivations $S \stackrel{+}{\Rightarrow} uAz,
	    A \stackrel{+}{\Rightarrow} vAy, A \stackrel{+}{\Rightarrow} x$, so that
	     $$uv^nxy^nz \in L_1$$ for all $n \geq 0$.
	    \item $x$ contains some $a$'s.
	    \item Either both $u$ and $v$ or both $y$ and $z$ contain some $a$'s.
	    \item $vxy$ contains less than $m$ $a$'s.
   \end{enumerate}
   Next we proof by contradiction, assume $L_1$ is context-free and show those four
   properties contradicts.  
   \begin{itemize}
	   \item First, it is trivial that the ``pumping part'' $v$ and $y$ can only contain
	   ``pure'' $a$, $b$ or $c$. Otherwise like if $v = a^sb^t$, then $uv^2xy^2z = 
	   ua^sb^ta^sb^txy^2z \notin L_1$, which contradict the property (1).
	   \item From property (2), since $x$ contains some $a$'s, then $v$ can only contain
	   $a$'s if not empty. But notice that property (3) implies $vy \neq \epsilon$ which means
	   at least one of $v$ and $y$ is not empty. Now there are only three possibilities for $y$: 
	   \item If $y$ only contains $a$'s, then both $v$ and $y$ contains only $a$'s and 
	   at least one of them is not empty. Choose $n = 3n$, so $uv^nxy^nz$ has more $a$'s 
	   than $b$'s, therefore $uv^{3n}xy^{3n}z \notin L_1$, which contradicts property (1).
	   \item If $y$ only contains $b$'s, then $y$ and $z$ can not contain $a$'s, from property (3),
	   both $u$ and $v$ contains some $a$'s. Choose $n = 3p$, then $uv^nxy^nz$ contains more
	   $a$'s than $c$'s because $v \neq \epsilon$, then $uv^{3p}xy^{3p}z \notin L_1$, 
	   which contradicts property (1).
	   \item If $y$ only contains $c$'s, then $x$ contains ALL $b$'s.
	   For the same reason as above, $v$ contains some $a$'s
	   and thus not empty. Then $uv^{3n}xy^{3n}z$ contains more $a$'s than $b$'s and thus
	   $uv^{3n}xy{3n}z \notin L_1$, which contradicts property (1).
	   \item As we see above, all possibilities lead to contradiction and thus $L_1$ is not
	   context-free. 	    
   \end{itemize}
   
   \item For $L_2$.\\

         Following the hint, let $k$ be the integer of Odgen's lemma. Let $p=k!$ and consider
         $w = a^{2p}b^{2p}c^p$ with $c$'s distinguished. Proof by contradiction, assume $L_2$ is
         context-free and therefore exists $w = uvxyz$ satisfied Odgen's lemma.
         \begin{itemize}
           \item From propert (2), $x$ contains some $c$'s, so $y$ and $z$ can only contain $c$'s.
           As stated above, ``pumping part''$v$ and $y$ can only contain ``pure'' $a$'s, $b$'s 
           or $c$'s.
           \item $v$ can not contain both $a$'s and $b$'s, and $y$ can only contain $c$'s. So if 
           $v$ contains either one, say $a$'s, then $a$'s can be ``pumped'' but $b$'s can not.
           Choose the pumping $n = 2$, $uv^2xy^2z$ contains more $a$'s than $b$'s, therefore 
           $uv^2xy^2z \notin L_2$, which contradicts property (1). So $v$ can only contains $c$'s.
           \item Here we reach the fact that both $v$ and $y$ can only contain $c$'s. Notice at least
           one of them is not empty. So $c$'s is the only part that can be ``pumped''. From property (4),
           $vxy$ contains less than $k$ $c$'s. Suppose $v$ and $y$ contains $x$ $c$'s in total. Then
           $x < k$ and thus $x$ divides ${k!}$. Choose the pumping $n = {k!}/x + 1$, notice that $p = k!$ and 
           $vxy$ is all in $c$'s. Then $uv^nxy^nz = a^{2p}b^{2p}c^{p + k!} = a^{2p}b^{2p}c^{2p} \notin L_2$,
           which contradicts property (1).
           \item Hence, assumption fails and $L_2$ is not context-free.
         \end{itemize}
\end{itemize}  


\vspace{0.25cm}\noindent
{\bf Problem B2 Proof:}\\

\noindent {\bf(1) Explanation:} for each string $w$ in $L$, by
making each symbol in $w$ appear or disappear we can get a new
string $w'$.
$\tau(L)$ is made of all such strings like $w'$.\\

\noindent {\bf(2) Proof:} Let $n=|\Sigma|$ and each symbol in
$\Sigma$ is denoted as $a_i(1\leq i\leq n)$. Since $L$ and
$\tau(a_i)$ are all context-free languages, let $G=\{V,\Sigma,P,S\}$
be the CFG for $L$, and $G_i=\{V_i,\Sigma,P_i,S_i\}$ for
$\tau(a_i)$.\\

$\forall p\in P(P\in G)$, if $a_i\in p$ then replace $a_i$ with
$S_i(S_i\in G_i)$, in this way we get a new production set $P'$. Now
generate a new CFG: $G_{\tau}=\{V_{\tau},\Sigma,P_{\tau},S\}$, where
$V_{\tau}=V\cup V_1\cup V_2\cup...\cup V_n$, $P_{\tau}=P'\cup
P_1\cup P_2\cup...\cup P_n$. Now we prove that $G_{\tau}$ is the CFG
for $\tau(L)$ and therefore $\tau(L)$ is a context-free language.\\

(i) Claim that for every $w\in\Sigma^*$, if
$S\Longrightarrow_{G_{\tau}}w$ then $w\in\tau(L)$. Proof: by
definition of $G_{\tau}$ we know that $\exists u\in L$ so that
$\tau(u)=\tau(a_{i_1}a_{i_2}\cdot\cdot\cdot
a_{i_n})=\tau(a_{i_1})\tau(a_{i_2})\cdot\cdot\cdot\tau(a_{i_n})=S_{i_1}S_{i_2}\cdot\cdot\cdot
S_{i_n}\Longrightarrow w$. Since $u\in L$ and $\tau(u)\in \tau(L)$,
so $w\in\tau(L)$.\\

(ii) Claim that $\forall w\in\tau(L)$,
$S\Longrightarrow_{G_{\tau}}w$. Proof: by definition of $\tau(L)$,
$\exists u\in L$ so that $w\in\tau(u)$. Since $u\in L$,
$S\Longrightarrow_G u=a_{i_1}a_{i_2}\cdot\cdot\cdot
a_{i_n}=S_{i_1}S_{i_2}\cdot\cdot\cdot S_{i_n}\Longrightarrow
\tau(a_{i_1})\tau(a_{i_2})\cdot\cdot\cdot \tau(a_{i_n})=\tau(u)$.
Since $w\in \tau(u)$, we can know that
$S\Longrightarrow_{G_{\tau}}w$.\\

From the discussion above we know that $G_{\tau}$ is the CFG for
$\tau(L)$ and therefore $\tau(L)$ is a context-free language.\\

\vspace{0.25cm}\noindent
{\bf Problem B3}\\

\noindent
\textbf{(i) Proof:}\\

With the definition of $\tau_1$ and $R$, we can have:
$$L_2 = \{E^* \ptb{a_1}h(a_1) E^* \ptb{a_2}h(a_2) E^* \cdots E^* \ptb{a_n}h(a_n)E^* \ |\ h(a_1a_2\cdots a_n)\in L\} $$

We denote:
$$L'= \{\ptb{a_1}h(a_1) \ptb{a_2}h(a_2)\cdots \ptb{a_n}h(a_n)\ |\ h(a_1a_2\cdots a_n)\in L\}$$,
$$L'' = \left(\ptb{\Omega}\cup \{h(a) \ |\ a\in\Omega\}\right)^*$$.

\noindent
The $\leftarrow$ direction:\\

For any string $w \in L'$, since $a \in \Omega$ iff $\ptb{a} \in \ptb{\Omega}$, we can easily have $w \in  L''$. Meanwhile, notice that $L' = \{E^0 \ptb{a_1}h(a_1) E^0 \ptb{a_2}h(a_2) E^0 \cdots E^0 \ptb{a_n}h(a_n)E^0 \ |\ h(a_1a_2\cdots a_n)\in L\}$, which is a subset of $L_2$. Then we can conclude that:
$$ L' \subset L_2\cap L''$$

\noindent
The $\rightarrow$ direction:\\

For any string $w \in L_2 - L'$, there must be at least one symbol $E$ exist in $w$, since $E$ does not belong to the alphabet of $L''$, then $w \notin L''$. Mean while, for any string $w \in L'' - L'$, there must be two consecutive symbols $ab$, either $a,b \in \ptb{\Omega}$, or $a,b \in h(\Omega)$, $w$ is clearly not in $L_2$. Then we can conclude that:

$$ L_2\cap L'' \subset L'$$

With $\leftarrow$ and $\rightarrow$, we complete the proof.\\


\noindent
\textbf{(ii) Proof:}\\

\begin{itemize}
\item If $\epsilon\notin L$.
\\\end{itemize}

Notice that $L_2 = \tau_1(L) \cap R$, and in \textbf{(i)} we have already shown that:
$$L_2 = \{E^* \ptb{a_1}h(a_1) E^* \ptb{a_2}h(a_2) E^* \cdots E^* \ptb{a_n}h(a_n)E^* \ |\ h(a_1a_2\cdots a_n)\in L\} $$

Then we can have, according to the definition of $g()$:
$$g(L_2) = \{E^* a_1 E^* a_2 E^* \cdots E^* a_n E^* \ |\ h(a_1a_2\cdots a_n)\in L\} $$

Similarly, according to the definition of $\tau_2()$:
$$\tau_2(g(L_2)) = \{\Gamma^* a_1 \Gamma^* a_2 \Gamma^* \cdots \Gamma^* a_n \Gamma^* \ |\ h(a_1a_2\cdots a_n)\in L\} $$

Notice that $\Gamma = \{a\in \Sigma\ |\ h(a) = \epsilon\}$, and $h()$ is a homomorphism, by simply apply $h()$, we will have:
\begin{enumerate}
 \item For all the string $w \in \tau_2(g(L_2))$, $h(w) \in L$.
 \item For all the string $w \in L$, $h^{-1}(w) \in \tau_2(g(L_2))$.
\end{enumerate}

Then we prove: $\tau_2(g(\tau_1(L)\cap R)) = h^{-1}(L).$\\

\begin{itemize}
\item If $\epsilon\in L$.
\\\end{itemize}

Apply the conclusion above, we already have: $\tau_2(g(\tau_1(L-\{\epsilon\})\cap R)) = h^{-1}(L-\{\epsilon\}).$\\

Notice that $\Gamma = \{a\in \Sigma\ |\ h(a) = \epsilon\}$, then $h^{-1}(\epsilon) = \Gamma^*$.\\

With above, we have the proof: $h^{-1}(L) = \tau_2(g(\tau_1(L - \{\epsilon\})\cap R)) \cup \Gamma^*.$\\


\noindent
\textbf{(iii) Proof:}\\

We already know that any regular languages are context-free at the same time. Besides, We also have:
\begin{itemize}
 \item If $L$ is a context-free language, in \textbf{Problem B2}, we have already proved that it is closed under substitution by other context-free languages, which is a stronger conclusion than $L$ is closed under substitution by regular languages.
 \item In \textbf{Homework 4, Problem B5}, we already proved that context-free languages are closed under intersection with regular languages.
 \item It is easily to show that context-free languages are closed under union with regular languages, we can have CFGs for both the context-free language $L_C$, and the regular language $L_R$, and introduce new start symbol to merge the two CFGs. That is to say, context-free languages are closed under union with regular languages.
\end{itemize}

Then we can have context free languages is such a family of languages stated in \textbf{(ii)}, which is closed under inverse homomorphisms. Then we complete the proof.\\

\vspace {0.25cm}
\noindent
{\bf Problem B4}\\

\noindent
\textbf{(a) Proof:}\\

PDA $M=\{ Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\}$

\begin{itemize}
\item $Q=\{q_0,q_1,q_2\}$
\item $\Sigma=\{a,b\}$
\item $\Gamma=\{Z_0,A,B\}$
\item $F=\{q_2\}$
\end{itemize}

In $\delta$, we have:
\begin{itemize}
 \item $(q_1,\epsilon) \in \delta(q_0,\epsilon,Z_0)$
 \item $(q_1,A) \in \delta(q_0,a,Z_0)$
 \item $(q_1,B) \in \delta(q_0,b,Z_0)$
 \item $(q_1,AA) \in \delta(q_1,a,A)$
 \item $(q_1,AB) \in \delta(q_1,a,B)$
 \item $(q_1,BA) \in \delta(q_1,b,A)$
 \item $(q_1,BB) \in \delta(q_1,b,B)$
 \item $(q_2,A) \in \delta(q_1,\epsilon,A)$
 \item $(q_2,B) \in \delta(q_1,\epsilon,B)$
 \item $(q_2,\epsilon) \in \delta(q_2,a,A)$
 \item $(q_2,\epsilon) \in \delta(q_2,b,B)$
\end{itemize}

$L_5=N(M)$.\\

Justification:\\

For PDA $M$, in state $q_1$, every letter in string $w$, the corresponding symbol $A,B$ will be push into the stack.
In the middle of string $ww^R$, state $q_1$ will go to $q_2$ by taking a $\epsilon$-transition.
In state $q_2$, every letter in string $w^R$ will pop the corresponding symbol $A,B$ from the stack.
Since the stack is ``last-in-first-out'', then we must have all the strings accepted by $N(M)$ are in the form $ww^R$.\\

\noindent
\textbf{(b) Proof:}\\

PDA $M=\{ Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\}$

\begin{itemize}
\item $Q=\{q_0,q_1\}$
\item $\Sigma=\{a,b\}$
\item $\Gamma=\{Z_0,A,B\}$
\item $F=\{q_1\}$
\end{itemize}

In $\delta$, we have:
\begin{itemize}
 \item $(q_0,ABB) \in \delta(q_0,a,Z_0)$
 \item $(q_1,ABBA) \in \delta(q_0,a,A)$
 \item $(q_1,\epsilon) \in \delta(q_0,b,A)$
 \item $(q_1,\epsilon) \in \delta(q_1,b,A)$
 \item $(q_1,\epsilon) \in \delta(q_1,b,B)$
 \item $(q_1,\epsilon) \in \delta(q_1,\epsilon,B)$
\end{itemize}

$L_6=N(M)$.\\

Justification:\\

For PDA $M$, in state $q_0$, every letter $a$ in the string, symbol $ABB$ will be push into the stack.
For the first $b$ in the string, state $q_0$ will go to $q_1$.
In state $q_1$, letter $a$ will halt the PDA, for every letter $b$ in the rest of string, it will pop corresponding symbol $A,B$ from the stack.
Symbol $B$ can be pop from the stack by taking a $\epsilon$-transition.
Then we have the language accepted by $N(M)$ is $L_6$.\\

\noindent
\textbf{(c) Proof:}\\

PDA $M=\{ Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\}$

\begin{itemize}
\item $Q=\{q_0,q_1, q_2, q_3, q_4\}$
\item $\Sigma=\{a,b\}$
\item $\Gamma=\{Z_0,A,B\}$
\item $F=\{q_3, q_4\}$
\end{itemize}

In $\delta$, we have:
\begin{itemize}
 \item $(q_1,Z_0) \in \delta(q_0,\epsilon, Z_0)$
 \item $(q_2,Z_0) \in \delta(q_0,\epsilon, Z_0)$

 \item $(q_1,A) \in \delta(q_1,a,Z_0)$
 \item $(q_1,AA) \in \delta(q_1,a,A)$

 \item $(q_2,A) \in \delta(q_2,a,Z_0)$
 \item $(q_2,B) \in \delta(q_2,a,A)$
 \item $(q_2,AB) \in \delta(q_2,a,B)$

 \item $(q_3,\epsilon) \in \delta(q_1,b,A)$
 \item $(q_3,\epsilon) \in \delta(q_3,b,A)$

 \item $(q_4,\epsilon) \in \delta(q_2,b,B)$
 \item $(q_4,\epsilon) \in \delta(q_4,b,B)$
\end{itemize}

$L_7=N(M)$.\\

Justification:\\

If string $w$ is in the form of $a^nb^n$, $q_0$ will go to $q_1$ by taking a $\epsilon$-transition; If string $w$ is in the form of $a^{2n}b^n$, $q_0$ will go to $q_2$ by taking a $\epsilon$-transition. 

In state $q_1$, every letter $a$ in the string will be push into the stack with symbol $A$.
For the first $b$ in the string, state $q_1$ will go to $q_3$.In state $q_3$, letter $a$ will halt the PDA, for every letter $b$ in the rest of string, it will pop corresponding symbol $A$ from the stack.

In state $q_2$, every two letter $a$ in the string will be push into the stack with symbol $B$.
For the first $b$ in the string, state $q_2$ will go to $q_4$.
In state $q_4$, letter $a$ will halt the PDA, for every letter $b$ in the rest of string, it will pop corresponding symbol $B$ from the stack.

Then we have the language accepted by $N(M)$ is $L_7$.\\

\noindent
\textbf{(d) Proof:}\\

PDA $M=\{ Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\}$

\begin{itemize}
\item $Q=\{q_0,q_1, q_2, q_3, q_4, q_5, q_6, q_7, q_8\}$
\item $\Sigma=\{a,b\}$
\item $\Gamma=\{Z_0, Z_1, A,B,C\}$
\item $F=\{q_4, q_4\}$
\end{itemize}

In $\delta$, we have:
\begin{itemize}
 \item $(q_1,Z_0) \in \delta(q_0,\epsilon, Z_0)$
 \item $(q_5,Z_0) \in \delta(q_0,\epsilon, Z_0)$

 \item $(q_1,AZ_0) \in \delta(q_1,a,Z_0)$
 \item $(q_1,BA) \in \delta(q_1,a,A)$
 \item $(q_1,AB) \in \delta(q_1,a,B)$
 \item $(q_2,B) \in \delta(q_1,b,B)$

 \item $(q_2,B) \in \delta(q_2,b,B)$
 \item $(q_3,\epsilon) \in \delta(q_2,a,B)$

 \item $(q_3,\epsilon) \in \delta(q_3,a,A)$
 \item $(q_3,\epsilon) \in \delta(q_3,a,B)$
 \item $(q_4,Z_0) \in \delta(q_3,b,Z_0)$

 \item $(q_4,Z_0) \in \delta(q_4,b,Z_0)$
 \item $(q_4,\epsilon) \in \delta(q_4,\epsilon,Z_0)$

 \item $(q_5,Z_1) \in \delta(q_5,a,Z_0)$
  \item $(q_5,Z_1) \in \delta(q_5,a,Z_1)$
 \item $(q_6,AZ_0) \in \delta(q_5,b,Z_1)$

 \item $(q_6,BA) \in \delta(q_6,b,A)$
 \item $(q_6,CB) \in \delta(q_6,b,B)$
 \item $(q_6,AC) \in \delta(q_6,b,C)$
 \item $(q_7,C) \in \delta(q_6,a,C)$

 \item $(q_7,C) \in \delta(q_7,a,C)$
 \item $(q_8,\epsilon) \in \delta(q_7,b,C)$

 \item $(q_8,\epsilon) \in \delta(q_8,b,A)$
 \item $(q_8,\epsilon) \in \delta(q_8,b,B)$
 \item $(q_8,\epsilon) \in \delta(q_8,b,C)$
 \item $(q_8,\epsilon) \in \delta(q_8,\epsilon,Z_0)$
\end{itemize}

$L_7=N(M)$.\\

Justification:\\

If string $w$ is in the form of $a^{2m}b^na^{2m}b^p$, $q_0$ will go to $q_1$ by taking a $\epsilon$-transition; if string $w$ is in the form of $a^{m}b^{3n}a^{p}b^{3n}$, $q_0$ will go to $q_5$ by taking a $\epsilon$-transition. \\

In state $q_1$, every two letter $a$ in the string will be push into the stack with symbol $AB$.
The PDA will halt if there is only odd number of $a$ before the first $b$ in the string.
For the first $b$ in string, state $q_1$ will go to $q_2$. For the first $a$ in rest of the string, state $q_2$ will go to $q_3$.
In state $q_3$, for every letter $a$ in the rest of string, it will pop corresponding symbol $AB$ from the stack, the occurrence of $b$ will lead to state transition form $q_3$ to $q_4$. In state $q_4$, the PDA will halt if there is $a$.\\

Similarly, in state $q_5$, there must be at least one $a$ before $b$, otherwise the PDA will halt. The first $b$ in the string will lead to state transition from $q_5$ to $q_6$.In $q_6$, $b$ will push $ABC$ into the stack, and the PDA will halt if the number of $b$ is not the multiple of $3$. For the first $a$ in the rest of the string, state $q_6$ will go to $q_7$. 
For the first $b$ in rest of the string, state $q_7$ will go to $q_8$.\\

In state $q_8$, for every letter $b$ in the rest of string, it will pop corresponding symbol $ABC$ from the stack. No $a$ is allow to occur in $q_8$.

Then we have the language accepted by $N(M)$ is $L_7$.\\

\noindent
\textbf{(e) Proof:}\\

PDA $M=\{ Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\}$

\begin{itemize}
\item $Q=\{q_0,q_1, q_2\}$
\item $\Sigma=\{a,b\}$
\item $\Gamma=\{Z_0,A\}$
\item $F=\{q_2\}$
\end{itemize}

In $\delta$, we have:
\begin{itemize}
 \item $(q_0,A) \in \delta(q_0, a, Z_0)$
 \item $(q_0,A) \in \delta(q_0, b, Z_0)$
 \item $(q_0,AA) \in \delta(q_0, a, A)$
 \item $(q_0,AA) \in \delta(q_0, b, A)$
 \item $(q_1,A) \in \delta(q_0, c, A)$
 \item $(q_1,Z_0) \in \delta(q_0, c, Z_0)$

 \item $(q_2,\epsilon) \in \delta(q_1,\epsilon,Z_0)$
 \item $(q_2,\epsilon) \in \delta(q_1,a,A)$
 \item $(q_2,\epsilon) \in \delta(q_1,b,A)$

 \item $(q_2,\epsilon) \in \delta(q_2,a,A)$
 \item $(q_2,\epsilon) \in \delta(q_2,b,A)$
\end{itemize}

$L_7=N(M)$.\\

Justification:\\

For PDA $M$, in state $q_0$, every letter in the string, symbol $A$ will be push into the stack.
For the first $c$ in the string, state $q_0$ will go to $q_1$, and $q_1$ will go to $q_2$ in the next.
In state $q_2$, for every letter in the rest of string, it will pop corresponding symbol $A$ from the stack.
Symbol $Z_0$ can be pop from the stack by taking a $\epsilon$-transition.
Then we have the language accepted by $N(M)$ is $L_9$.\\


\vspace {0.25cm}
\noindent
{\bf Problem B5}\\

\noindent
{\bf Proof:}\\

\medskip\noindent
\textbf{(i)} From pumping lemma, there exists $w = uvxyz$ such that $uv^nxy^nz \in L$ for all $n \geq 0$ and
   $vy \neq \epsilon$. Since $L \subseteq \{a\}^*$. Suppose $vy = a^x$, we know 
   $1 \leq x < K$, and thus $x$ divides $K!$. $\forall n \geq 0$, choose the pumping
   value $m = (1 + nK!/x)$, then $uv^mxy^mz$ = $wa^{nK!} = wa^{nr} \in L$. Therefore, 
   $\{wa^{rn} | n \geq 0 \} \subseteq L$.\\ 

\medskip\noindent
\textbf{(ii)} From definition $L_i = \{a^n \ |\ a^n\in L,\, n \geq K,\, n \equiv i \bmod r\}$,
next we prove that $L_i = \{z_i a^{rm}\ | \ m \geq 0\}$ by two steps.
\begin{itemize}
  \item Prove $L_i \subseteq \{z_i a^{rm}\ | \ m \geq 0\}$\\
  $\forall w \in L_i$, $w = a^n$ and $n = i + rt$ for some $t \geq 0$. $z_i$ is the shortest string in $L_i$,
  thus $z_i = i + rs$ for some $s \geq 0$, and $s \leq r$. Let $m = r - s \geq 0$, observe that 
  $n = i + rt = z_i + rm$, so $w = z_ia^{rm} \in \{z_i a^{rm}\ | \ m \geq 0\}$. So 
  $L_i \subseteq \{z_i a^{rm}\ | \ m \geq 0\}$.
  \item Prove $L_i \supseteq \{z_i a^{rm}\ | \ m \geq 0\}$\\
  $\forall w \in \{z_i a^{rm}\ | \ m \geq 0\}$. $z_i$ is the shortest string in $L_i$,
  thus $z_i = i + rs$ for some $s \geq 0$. $w = z_ia^{rm} = a^{i + (s+m)r}$, notice that $i + (s+m)r \equiv i \bmod r$,
  so $w \in L_i$ and therefore $L_i \supseteq \{z_i a^{rm}\ | \ m \geq 0\}$.
\end{itemize}
It is trivial to show $L_i$ is regular, actually we can write the equivalent regular expression explicitly as
$L_i = L(z_i(a^r)^*)$(it is also easy to construct a DFA accepting $L_i$). By $$L = \{a^n \ |\ a^n \in L,\, n < K\}
\cup \bigcup_{i = 0}^{r-1} L_i.$$ We know $L$ is the combination of some finite set and finite many
regular languages, therefore $L$ is regular.\\

\medskip\noindent
\textbf{(iii)}
Let $L'_i = \{a^n \ |n \geq K, \, n \equiv i \bmod r\}$. Clearly, $L_i = L'_i \bigcap L$.\\
From (ii), we can write the equivalent regular expression of $L'_i$ as $L'_i = L(a^x(a^r)^*)$ where $x$ is the smallest
integer such that $x \geq K, \, x \equiv i \bmod r$. Therefore $L'_i$ is regular.\\
We know $L'_i$ is regular and $L$ is context-free. Recall that in homework 4 Problem 6, we proved the following fact:
\begin{center}
``Given a context-free language $L$ and a regular language $R$, $L \bigcap R$ is context-free''.
\end{center} 
Therefore $L_i = L'_i \bigcap L$ is context-free. Then we can write the CFG of $L_i$ in CNF:\\
\begin{center}
(1) $A \rightarrow BC$\\
(2) $A \rightarrow a $\\
where $A,B,C \in N ,\ a \in \Sigma$(Notice that $\epsilon \notin L_i$).
\end{center}
Next we prove it is decidable whether $L_i = \phi$ by giving an algorithm explicitly. Suppose there are $n$ type(1) derivations
and $m$ type(2) derivations in CFG of $L_i$\\
\begin{enumerate}
  \item Start. Set $S_1 = S_2 = \phi$.
  \item for i = 1 to m \\
          $S_1$ = $S_1$ + \{Non-terminal at left-side of i-th type(2) derivation\}.
  \item $S_2 = S_1$.
  \item for i = 1 to n\\
        \{\\
            if(All Non-terminals at right side of i-th type(1) derivation is IN $S_2$)\\
               $S_2$ = $S_2$ + \{Non-terminal at the left-side of i-th type(1) derivation\};\\
        \}  
  \item while ($S_1 \neq S_2$)\\
        \{\\
          $S_1 = S_2$;\\
          for i = 1 to n\\
          \{\\
            if(All Non-terminals at right side of i-th type(1) derivation is IN $S_2$)\\
               $S_2$ = $S_2$ + \{Non-terminal at the left-side of i-th type(1) derivation\};\\
          \}\\ 
        \}
  \item If(Start symbol $S \in S_1$)\\
           return $L_i \neq \phi$\\
        Else\\
           return $L_i = \phi$.
\end{enumerate}
We claim our program is correct by noting that
the key idea is starting from terminals, tracing back and put all Non-terminals start from
which there exists a derivation chain to terminals into a set $S$. Check whether starting symbol is in the set $S$.
If true, then it means there exists a derivation chain from starting symbol to any terminal, which implies 
$L_i \neq \phi$, else $L_i = \phi$. What our program do is as follows:
\begin{enumerate}
  \item Put all Non-terminals at left-side of type(2) derivation into a set $S$.
  \item (tracing back step) For all type(1) derivation, if all right-side Non-terminals of a derivation is in $S$,
        then put the left-side Non-terminal of that derivation into set $S$.
  \item Repeat step 2 until $S$ stop expanding. (the algorithm is guaranteed to terminate because there are ony finitely
        many Non-terminals and thus $S$ can not expand forever).
  \item Check whether starting symbol is in $S$.
\end{enumerate}
Therefore, by proving that $L_i$ is context-free and given a context-free grammer, there exists a algorithm to check
whether there exists a derivation chain from starting symbol to any terminal, we reach the fact that it is decidable
whether $L_i = \phi$.


\medskip\noindent
\textbf{(iv)}
We prove by giving an explicit algorithm and prove it actually decide whether $\{a\}^* \subseteq L$.
\begin{enumerate}
  \item Start. $i = 0$.
  \item Check whether $a^i \in L$.
  \item If(true and $i < r + K - 1$), $i = i + 1$, go to step 2.\\
        Else if(true and $i = r + K - 1$), return true. \\
        Else, return false.
  \item end.
\end{enumerate}
This algorithm simply check whether for all $i$ such that $0 \leq i \leq (r + K - 1)$, $a^i \in L$.
Next we prove it actually decide whether $\{a\}^* \subseteq L$.
\begin{itemize}
  \item If return True.\\
  Then $\forall x \geq 0$, if $x < K$, then $a^x \in L$; if $x > K$, there $\exists K \leq y \leq (r + K -1)$
  such that $x \equiv y \bmod r$, we know $a^{y} \in L$, from (i), $a^x \in L$. Hence, $\forall x \geq 0, a^x \in L$.
  which means $\{a\}^* \subseteq L$.
  \item If return False.\\
  Then we found a $w \in \{a\}^*$ but $w \notin L$. Hence we know $\{a\}^* \not\subseteq L$.
\end{itemize}
Hence, our algorithm decide whether $\{a\}^* \subseteq L$.\\

\vspace {0.25cm}\noindent
{\bf Problem B6}\\

\noindent {\bf Proof:}\\

\noindent(1): The CFG for $D_2$ is $G_2=\{V,\Sigma_2,P,S\}$, where
$V=\Sigma_2\cup\{S,S_1,S_1^{'},S_2,S_2^{'}\}$, and $P$ is the following:

\begin{center}
$S\rightarrow\epsilon,$\\

$S\rightarrow SS_1SS_1^{'}S,$\\

$S\rightarrow SS_2SS_2^{'}S,$\\

$S_1\rightarrow a, S_1^{'}\rightarrow \overline a,$\\

$S_2\rightarrow b, S_2^{'}\rightarrow \overline b$.\\\end{center}

\noindent Justification: \\

By definition of $D_2$, $\epsilon\in D_2$,
and we have production $S\rightarrow\epsilon$ to achieve this. In
further, by induction suppose we have $S\Rightarrow_{G_2} D_2$. By
definition, if $x,y,v\in D_2$ and $v=xy$, then $u=xa\overline ay\in
D_2$. This can be achieved by production $S\rightarrow SS_1S_1^{'}S,
S_1\rightarrow a, S_1^{'}\rightarrow \overline a$. The same holds
for $u=xb\overline
by\in D_2$. Therefore $G_2$ is the CFG for $D_2$.\\

\noindent(2): The CFG for $D_m$ is $G_m=\{V,\Sigma_2,P,S\}$, where
$V=\Sigma_m\cup\{S,S_1,S_1^{'},S_2,S_2^{'},\cdot\cdot\cdot
,S_m,S_m^{'}\}$, and $P$ is the following:

\begin{center}
$S\rightarrow\epsilon,$\

$S\rightarrow SS_1SS_1^{'}S,$\

$S\rightarrow SS_2SS_2^{'}S,$\

$\cdot\cdot\cdot$\

$S\rightarrow SS_mSS_m^{'}S$\

$S_1\rightarrow a_1, S_1^{'}\rightarrow \overline {a_1},$\

$S_2\rightarrow a_2, S_2^{'}\rightarrow \overline {a_2},$\

$\cdot\cdot\cdot$\

$S_m\rightarrow a_m, S_m^{'}\rightarrow \overline {a_m}$.\\\end{center}

\noindent
Proof:

\begin{itemize}
 \item By definition of $D_m$, $\epsilon\in D_m$, and we have production $S\rightarrow\epsilon$ to achieve this.
 \item For all the string $w \neq \epsilon$, $w\in D_m$. Notice that for all the strings $w \in D_m$, the length of $w$ is even. Assume $|w|=i$, prove by induction:
\begin{enumerate}
 \item If $i=2$, all the strings $w$ can be generate by the grammar $G_m$ is $a_i\overline {a_i}, (i=1 \cdots m)$; all the string $w' \in D_m (|w'|=2)$ is the same set, so we have $G_m$ is the CFG for $D_m$, when $|w|=2$;
 \item Assume when $i \leq 2n$, $G_m$ is the CFG for $D_m$, where $|w|=i$;
 \item When $i = 2n+2$, for any string $w \in D_m, |w|=2n+2$, go through the string $w$ from left to right, let current pointer $p$ point to the start symbol $S$:
\begin{itemize}
 \item If the ith letter in $w$ is $a_i$, derive the pointing $S$ using $S\rightarrow SS_i\textbf{S}S_i^{'}S,$\, pointer $p$ point to the new bold \textbf{S}.
 \item If the ith letter in $w$ is $\overline {a_i}$, pointer $p$ point to the next $S$.
 \item After consume all the letter in $w$, apply grammar rule $S\rightarrow\epsilon$ and $S_i\rightarrow a_i, S_i^{'}\rightarrow \overline {a_i}$.

With the algorithm above, we have all the string $w \in D_m$ can be generated by CFG $G_m$.\\

For all the string $w$ generated by CFG $G_m$, $|w|= 2n+2$, by induction hypothesis, we already have all the $w'$ generated by CFG $G_m$, $|w'|= 2n$, $w' \in D_m$, following the algorithm above, we can see that to generate $w$ we need to apply one additional grammar rules $S\rightarrow SS_iSS_i^{'}S$\ comparing to the generation of $w'$, that is easy to show that $w \simeq w'$, then we have all the string $w$ generated by CFG $G_m$, $w \in D_m$.
\end{itemize}


\end{enumerate}

\end{itemize}


 

By induction, we proved $G_m$ is the CFG for $D_m$. \\


\end{document}
